1. Field of the Invention
The present invention relates to a high-efficiency encoding apparatus used in a digital signal recording/reproduction apparatus such as a digital video tape recorder (called digital VTR hereafter) which records digital video information, particularly to a high-efficiency encoding apparatus which encodes digital data while compressing the amount of data, and to a high-efficiency decoding apparatus which corresponds to the high-efficiency encoding apparatus.
2. Description of Related Art
FIG. 1 is a block diagram illustrative of the constitution of a high-efficiency encoding apparatus of the prior art. In FIG. 1, numeral 1 denotes a shuffling circuit whereto digital video data including a luminance signal and two kinds of color difference signals are inputted. The shuffling circuit 1 arranges the digital video data, namely the luminance signal and the two kinds of color difference signals, into a block structure with each block consisting of 8 pixels.times.8 lines (the block will be called the DCT block hereafter), then shuffles the data in the unit of DCT blocks in a predetermined order and outputs the resultant data to a DCT transformer 2. The DCT transformer 2 applies discrete cosine transformation (called DCT transformation hereafter) to the incoming DCT blocks and outputs the DCT coefficients to a quantizer 3. The quantizer 3 quantizes the DCT coefficients with a predetermined value and outputs the DCT data to a data division circuit 7. The data division circuit 7 separates the DCT data received from the quantizer 3 into 0-run length data and coefficient data, and outputs them to a variable-length encoder 4. The variable-length encoder 4 applies variable-length encoding to the output of the data division circuit 7 and outputs the encoded data to a buffer 5. The buffer 5 temporarily stores the variable-length encoded data. A rate control circuit 6 measures the amount of data which is inputted to the buffer 5, and controls the quantization level of the quantizer 3 according to the amount of measured data.
Now the operation will be described below. Inputted digital video data is structured by the shuffling circuit 1 into DCT blocks each comprising 8 lines vertically and 8 pixels per line, then shuffled in the unit of the DCT block. In the description that follows, the value of data located at line i, column j in a DCT block will be represented by f(i, j) where i and j are spatial coordinates. 64 pixels of data in a DCT block which has been shuffled are DCT-transformed in the DCT transformer 2. DCT transformation will be briefly described below. The transform is carried out by calculating the following equation. ##EQU1## where x, y are spatial coordinates, u, v are Fourier transformation coordinates, ##EQU2##
Result of the transformation is obtained in the form of 8.times.8 data blocks as shown in FIG. 2 or FIG. 3. Data of line u, column v is denoted as F(u, v). In a data block, data of sequence No. 0 located at the top left corner is called the DC coefficient, data from sequences 1 through 63 are called AC coefficients, of which those of smaller sequence numbers are called the low-frequency coefficients and those of larger sequence numbers are called the high-frequency coefficients. DCT-transformed data generally has power spectrum concentrated in low-frequency components. Coefficients obtained in the DCT transformation are outputted from the DCT transformer 2 successively in order starting with the data in the low-frequency region where the power spectrum is concentrated, while being scanned in a method called zig-zag scanning in the order of sequence numbers shown in FIG. 3. The order of output is shown by arrows in FIG. 2. Data is outputted successively from sequence 0 to sequence 63 as shown in the drawing.
Data after orthogonal transformation is inputted to the quantizer 3 where it is quantized. FIG. 4 is a block diagram illustrative of the inner constitution of the quantizer 3. In FIG. 4, the quantizer 3 has an input terminal 3a for the DCT coefficients F(u, v) which are outputted from the DCT transformer 2, an input terminal 3b to receive quantization table values T(u, v), a multiplier 3c, a divider 3d, a rounding circuit 3e to round off the output from the divider 3d to a specified number of bits, and an output terminal 3f. The quantization table is a table containing 8.times.8 predetermined values as shown in FIG. 5. Similarly to the case of the DCT coefficients, value contained at line u, column v of the table will be denoted as T(u, v).
The operation of the quantizer 3 will now be described below with reference to FIG. 4. First, in the multiplier 3c, the quantization table value T(u, v) which is inputted from the input terminal 3b is multiplied with a rate control variable K which is outputted from the rate control circuit 6. The DCT transform coefficient F(u, v) which is inputted to the input terminal 3a is divided in the divider 3d by the result of multiplication by the multiplier 3c. The result of the dividing operation is rounded to an appropriate number of significant digits in the rounding circuit 3e. The rounding circuit 3e outputs the result to the output terminal 3f. This operation can be mathematically represented as follows. ##EQU3## where round (x) represents the operation of rounding the value x to a specified number of significant digits.
The operation of the data division circuit 7 will be described below. In a high-efficiency encoding apparatus commonly used in the compression of video data, 2-dimensional Huffman coding technique is used in the variable length encoder 4. In the 2-dimensional Huffman coding, DCT data which is read from the DCT transformer 2 by zig-zag scanning and then quantized is divided into non-zero coefficients and the number of 0's terms (0-run length) before being encoded. This means that coding is carried out by preparing a coding table which gives an appropriate code length (the number of bits) according to the occurrence probability of an event represented by the number of 0's (0-run length) between two non-zero coefficients, and the coefficient following the zero, then the events of the 0-run length data and the coefficient data are subjected to variable-length encoding, thereby to obtain 2-dimensional Huffman-coded data. In this process, shorter codes are assigned to more frequently appearing events and longer codes are assigned to less frequently appearing events. Thus the data division circuit 7 converts the incoming DCT data into an event of 0-run length data and coefficient data. In the description that follows, an operation to separate the data into a length of the runs of a particular coefficient A and other coefficients other than A such as in the data division circuit 7 will be called A-run length coding.
The event of 0-run length data and coefficient data separated in the data division circuit 7 is inputted to the variable length encoder 4. The variable length encoder 4 will be described below. FIG. 6 is a block diagram illustrative of the inner construction of a conventional variable length encoder commonly used. In FIG. 6, the variable length encoder 4 is constituted from an encoder 4a and a coding table 4b which are connected to each other by signal lines 4c, 4d. The 0-run length data and coefficient data which are outputted from the data division circuit 7 are read by the encoder 4a so that codes are obtained via the signal line 4c while making reference to the coding table 4b via the signal line 4d according to the input data, thereby to output digital signals. It is assumed here that 2-dimensional Huffman codes are recorded in advance in the coding table.
The principle of reducing the amount of codes by means of the variable length codes (Huffman codes) used in this example of the prior art will be described briefly below. The coding table 4b is prepared to make the bit length of coded data variable according to the occurrence probability of the input data. That is, assuming the occurrence probability of data Di be Pi and the code length after encoding in the case of Pi be Li, then when occurrence probabilities of input data Dj, Dk are in the relation of inequality EQU Pj&gt;Pk,
the total amount of encoded data can be reduced from that of the input data by making the code lengths after encoding satisfy the inequality; EQU Lj.ltoreq.Lk
Suppose a case where four kinds of input data having fixed length of 6 bits; 0, 10, 20, 30, have occurrence probabilities of 50%, 30%, 10% and 10%, respectively, and the code given in FIG. 7 is assigned to each piece of data in the ascending order of occurrence probability. While an input data stream of 0, 20, 0, 0, 30, 10, 0, 10, 0, 10, for example, requires total number of bits of 6 bits/word.times.10 words=60 bits, use of the table shown in FIG. 7 enables it to encode the entire data stream with 17 bits, thereby reducing the total amount of data.
Coded data thus compressed is then fed to the buffer 5 which stores the coded data temporarily. On the other hand, the rate control circuit 6 measures the amount of coded data which has been stored in the buffer 5 up to that time. And accordingly sends a rate control variable K to the quantizer 3 so that the final amount of codes becomes an appropriate value.
A high-efficiency encoding apparatus of the prior art is constituted as described above. The result of a simulation of high-efficiency encoding operation on 1-frame video data using the high-efficiency encoding apparatus will be described below with reference to FIG. 8 and FIG. 9.
FIG. 8 is a drawing illustrative of an array of data obtained through simulation of 0-run length coding, showing the 2-dimensional distribution of the 0-run length data and coefficients of a luminance signal. The description that follows will be restricted to the luminance signal. In FIG. 8, coefficients are arranged from left to right, and 0-run length data is arranged from top to bottom. The element having a coefficient of 0 and 0-run length data of 0 is EOB (end of block). In FIG. 8, terms having both positive and negative values are counted for the coefficient data. For example, number of coefficients having a value 1 is given by adding the number of terms having a value 1 and the number of terms having a value -1. Huffman code length data obtained by transforming the 2-dimensional data array shown in FIG. 8 into 2-dimensional Huffman code array is shown in FIG. 9. In FIG. 9, coefficient data is arranged from left to right, and 0-run length data is arranged from top to bottom. This simulation was conducted by using quantization table values shown in FIG. 5 and a rate control variable fixed to 43. Huffman codes are represented by assigning 1 codeword to each term of data occupying 99.4% of all events and assigning escape codes to the rest of terms. FIG. 9 shows the result of simulation conducted on AC coefficients only. The code denoted by numeral 101 is a dummy code merely filling the space which is empty for the reason of 0-run length data.
The simulation showed that the transmitted data required for the transmission of luminance signal data for one frame used in the test image was 701,771 bits in the case of handling AC coefficients only. Because Huffman coding of DC coefficients generally does not lead to significant reduction of the amount of data, DC coefficients are often sent directly in the form of raw values. In this example of the prior art too, they are also assumed to be sent in the form of raw values.
In the high-efficiency encoding apparatus of the prior art, as described above, while the amount of transmitted codes of incoming video signals for one frame is reduced by using DCT transformation and variable length encoding, the recording capacity of storage media such as digital VTR is limited and recording of high-quality video signals with a limited recording capacity requires further reduction of the amount of data. Transmission of AC coefficients, in particular, requires as much as 701,771 bits for one frame as described above, and further reduction of the amount of data is called for.
Now a high-efficiency decoding apparatus of the prior art will be described below. FIG. 10 is a block diagram illustrative of the constitution of the conventional high-efficiency decoding apparatus. In FIG. 10, numeral 301 denotes a variable-length decoder which applies variable length decoding to the input data. The variable length decoder 301 feeds the decoded data (run-length data and coefficient data) to a data synthesis circuit 302. The data synthesis circuit 302 synthesizes the run-length data and the coefficient data and sends DCT data to an inverse quantizer 303. The inverse quantizer 303 inverse-quantizes the DCT data and sends the DCT coefficients to an inverse DCT transformer 304. The inverse DCT transformer 304 applies inverse DCT transformation to the DCT coefficients and sends the original video data to a deshuffling circuit 305. The deshuffling circuit 306 arranges the DCT blocks into the original order and outputs the original video signals. FIG. 11 is a block diagram illustrative of the inner constitution of the variable length decoder 301 shown in FIG. 10. The variable-length decoder 301 has an input terminal 310 for data input, an input terminal 311 for a variable-length decoding start signal which indicates the start point of the incoming variable-length codes, a shift register 312, a code conversion ROM table 313 to convert the incoming 2-dimensional Huffman codes into the original run-length data and the coefficient data, a code length ROM table 314 which outputs the code length data of the incoming 2-dimensional Huffman codes, a register control circuit 315 which controls the shift amount of the shift register 312 according to the code length information supplied by the code length ROM table 314, an output terminal 316 for the run length data, an output terminal 317 for the coefficient data, and an output terminal 318 which is used for the output of the run length data and the coefficient data supplied through the output terminals 316 and 317, a control signal to indicate the effective area of the run-length data and the coefficient data, a control signal to indicate the start point of the DCT block detected from the 2-dimensional Huffman codes and other signals (collectively called data synthesis control signal hereafter).
FIG. 12 is a block diagram illustrative of the inner constitution of the data synthesis circuit 302 shown in FIG. 10. The data synthesis circuit 302 has an input terminal 320 for the coefficient data, an input terminal 321 for the run-length data, an input terminal 322 for the data synthesis control signal, a memory 323, a memory control circuit 324 to control write/read operation of the memory 323 and an output terminal 325 for data.
Now the operation of the variable-length decoding apparatus of the prior art constituted as described above will be described below. A 1-bit serial data stream is inputted to the variable-length decoder 301. The variable-length decoder 301 transforms the incoming 1-bit serial data stream into run-length data and coefficient data. The 1-bit serial data which is inputted via the input terminal 310 is inputted to the shift register 312 where it is converted to parallel data. The output of the shift register 312 is inputted to the code conversion ROM table 313 and to the code length ROM table 314. The code conversion ROM table 313 converts the variable length code which is outputted from the shift register 312 to the original run-length data and the coefficient data. On the other hand, the code length ROM table 314 outputs the code length information of the incoming variable length code to the register control circuit 315. The register control circuit 315 controls the shift amount of the shift register 312 according to the code length information and, at the same time, outputs the data synthesis signal (a signal indicating the effective area of output data from the output terminals 316 and 317, a signal indicating the start point of the DCT block, etc.).
The output of the variable length decoder 301 is inputted to the data synthesis circuit 302. The operation of data synthesis will be described below. All data in a specified memory block in the memory 323 is set to zero according to the DCT block start point signal included in the data synthesis control signals which are inputted via the input terminal 322. In this example, it is assumed that two 64-byte memory blocks make a pair (128 bytes), and a plurality (generally equals the number of DCT blocks handled in controlling the amount of codes) of pairs constitute the memory 323. This constitution is employed so that, when data of a DCT block is being synthesized in one memory block, synthesized data is read in another memory block. The memory control circuit 324 writes the coefficient data to the address which indicates the run-length data according to the effective area signal incoming through the input terminal 322.
FIG. 13 is a drawing explanatory of the variable-length decoding operation of the prior art. FIG. 13A shows an event of run-length data and coefficient data, and FIG. 13B shows the result of synthesizing the data stream shown in FIG. 13A by means of the memory. The memory control circuit 324 generates the address of writing the coefficient data other than zeros shown in FIG. 13B according to the incoming run-length data, thereby carrying out the decoding operation.
The DCT data synthesized in the above operation is inverse-quantized in the inverse quantizer 303. The rate control variable K is generally transmitted together with the DCT data. The inverse DCT transformer 304 applies inverse DCT transform to restore the original video data. The deshuffling circuit 305 deshuffles the incoming DCT block to cancel the block structure and outputs the video signals.
In the high-efficiency encoding apparatus of the prior art, because it is constituted as described above, the amount of codes during high-efficiency coding has been suppressed by increasing the value of the rate control variable K which is inputted to the quantizer 3. However, although increasing the rate control variable K reduces the amount of codes, it also causes degradation of the picture quality. This is because the amount of codes after high-efficiency coding is greater than necessary in the high-efficiency encoding apparatus of the prior art.